## Copyright (C) 2012 Estela Moura
## 
## This program is free software; you can redistribute it and/or modify
## it under the terms of the GNU General Public License as published by
## the Free Software Foundation; either version 3 of the License, or
## (at your option) any later version.
## 
## This program is distributed in the hope that it will be useful,
## but WITHOUT ANY WARRANTY; without even the implied warranty of
## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
## GNU General Public License for more details.
## 
## You should have received a copy of the GNU General Public License
## along with Octave; see the file COPYING.  If not, see
## <http://www.gnu.org/licenses/>.

## NearestNeighborTSP

## Author: Estela Moura <estela@kubuntu-Inspiron>
## Created: 2012-06-14

function [BestTourLength, BestTour]=NearestNeighborTSP(distances_matrix)

% Nearest Neighbor Heuristic for the TSP
%
% NearestNeighborTSP(distances_matrix)
%
% distances_matrix: symmeric real (NrOfNodes x NrOfNodes)-matrix containing distances
% between all nodes: d[i,i] = 0, d[i,j]=d[j,i]
%
% returns [BestTourLength, BestTour]

d = distances_matrix;
n = max(size(d));

for i = 1 : n
  d(i,i) = inf;
end

b_Tour = 0;
b_Length = inf;

for m = 1 : n
  cur_T = m;
  cur_L = 0;
  to_visit = setdiff([1:n],cur_T); %retorna todos os nós, exceto o próprio nó do momento (cur_T).
  
  while (length(to_visit) > 0)
    cur_end = cur_T(length(cur_T));
    next_node = to_visit(1);
    for i = 2 : length(to_visit)
      if (d(cur_end,to_visit(i)) < d(cur_end,next_node))
      next_node = to_visit(i);
      end
    end
    cur_L = cur_L + d(cur_T(length(cur_T)),next_node);
    cur_T = [cur_T next_node];
    to_visit = setdiff(to_visit,next_node);
  end
  cur_L = cur_L + d(cur_T(length(cur_T)),cur_T(1));
  cur_T = [cur_T cur_T(1)];
  if (cur_L < b_Length)	
    b_Length = cur_L;
    b_Tour = cur_T;
  end
end

BestTourLength = b_Length;
BestTour = b_Tour;
endfunction
